package com.sheng.leetcode.year2022.month08.day25;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/08/25
 *
 * 4. 寻找两个正序数组的中位数
 *
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 *
 * 示例 1：
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 *
 * 示例 2：
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 *
 * 提示：
 *
 * nums1.length == m
 * nums2.length == n
 * 0 <= m <= 1000
 * 0 <= n <= 1000
 * 1 <= m + n <= 2000
 * -106 <= nums1[i], nums2[i] <= 106
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0004 {

    @Test
    public void test01() {
//        int[] nums1 = {1,3};
//        int[] nums2 = {2};
        int[] nums1 = {1,2};
        int[] nums2 = {3,4};
        System.out.println(new Solution4().findMedianSortedArrays(nums1, nums2));
    }
}
class Solution4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // 将两个数组合并，并对新数组进行排序
        int[] nums = Arrays.copyOf(nums1, m + n);
        System.arraycopy(nums2, 0, nums, m, n);
        Arrays.sort(nums);
        double result = 0d;
        int x = (m + n) / 2;
        if ((m + n) % 2 == 0) {
            // m + n为偶数
            result = (double) (nums[x - 1] + nums[x]) / 2;
        } else {
            result = nums[x];
        }
        return result;
    }
}
